Educational Codeforces Round 108 (Div. 2) B The Cake Is a Lie

手元で小さい例について実験してみると, 2×2の部分グリッドについて, 横→縦, 縦→横のどちらを通ってもコストは変わらないということがわかる. これより, 任意の大きさのグリッドについてどんなルートを通ってもコストは変わらないことがいえる. よって適当に一つのルートについて, そのコストを求めればよい.